import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 * 滑动窗口
 * 定义一个窗口，其大小可以是固定的，也可以根据具体问题动态变化。
将窗口放置在序列的起始位置，然后根据特定的规则在序列上滑动窗口。
在每个窗口位置，对窗口内的数据进行特定的计算或处理。

滑动窗口算法

滑动窗口算法其实和这个是一样的，只是用的地方场景不一样，可以根据需要调整窗口的大小，有时也可以是固定窗口大小。

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。
该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。


 */
public class 滑动窗口示例 {
    
    public static void main(String[] args) {

        try{

            //test1();
            //test2();
            //test3();
            //test4();
            //test5();
            test6();

        }catch(Exception e){

            e.printStackTrace();
        }

    }

    //1、给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
    //返回滑动窗口最大值。
    private static void test1(){

        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        int windowLen = 3;
        List<Integer> result = new ArrayList<>();

        for(int i=0; i<nums.length - windowLen +1; i++){
            int[] subArr = new int[windowLen];
            System.arraycopy(nums, i, subArr, 0, windowLen);

            //窗口中的和
            //int sum = Arrays.stream(subArr).reduce(0, Integer::sum);
            //窗口中的最大值
            int max = Arrays.stream(subArr).max().getAsInt();

            result.add(max);

        }


        result.stream().map(s -> s+",").forEach(System.out::print);
        System.out.println();

    }

    private static void test2(){

            String str = "accekcbbt";
            LinkedList<Character> resultList = new LinkedList<>();
            long maxLen = 0L;

            for(char c : str.toCharArray()){

                resultList.add(c);
                //去重
                maxLen = resultList.stream().distinct().count();

                if(resultList.size() != maxLen){
                    resultList.removeFirst();
                }

            }

            System.out.println("无重复字符的最长子串长度为：" + maxLen);
            
            // int n = s.length();
            // int[] index = new int[128];
            // int maxLen = 0;
            // int start = 0;
            // for (int end = 0; end < n; end++) {
            //     start = Math.max(start, index[s.charAt(end)]);
            //     maxLen = Math.max(maxLen, end - start + 1);
            //     index[s.charAt(end)] = end + 1;
            // }

            // System.out.println("无重复字符的最长子串长度为：" + maxLen);

            // System.out.println("无重复字符的最长子串长度为：" + ((int)"A".toCharArray()[0]));

    }

    private static void test3(){

        //给定一个整数数组和一个整数 k，
        //判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

        int[] nums = new int[]{1,2,3,1};
        int k = 3;

        LinkedList<Integer> resultList = new LinkedList<>();

        for(int i=0; i<nums.length; i++){

            if(resultList.contains(nums[i])){
                System.out.println(""+true);

                return;
            }

            resultList.add(nums[i]);

            if(resultList.size() > k){

                resultList.removeFirst();
            }
        }

        System.out.println(""+false);

    }

    private static void test4(){

        //给定一个含有 n 个正整数的数组和一个正整数 s ，
        //找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0；

        int[] nums = new int[]{2,3,1,2,4,3};
        int k = 7;
        int minLen = nums.length;

        int sum=0;
        LinkedList<Integer> numList = new LinkedList<>();

        for(int i=0; i<nums.length; i++){

            int num = nums[i];
            numList.add(num);
            sum += num;

            while (sum >= k) {

                minLen = Math.min(minLen, numList.size());
                sum -= numList.removeFirst();

            }


        }

        System.out.println(minLen+"");

    }

    private static void test5(){
        //给定一个由若干 0 和 1 组成的数组 A，
        //我们最多可以将 K 个值从 0 变成 1，返回仅包含 1 的最长（连续）子数组的长度；

        int[] nums = new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int k = 3;

        int zeroCout = 0;

        LinkedList<Integer> resultList = new LinkedList<>();

        for(int i=0; i<nums.length; i++){

            if(0 == nums[i]){
                zeroCout++;
            }

            if(zeroCout > k){
                int pop = resultList.removeFirst();
                if(0 == pop){
                    zeroCout--;
                }
            }


            resultList.add(nums[i]);

        }

        System.out.println(resultList.size());
    }

    private static void test6(){

        //给你字符串 s 和整数 k 。
        //请返回字符串 s 中长度为 k 的单个子字符串中，返回包含的最大元音字母的数量。
        //英文中的 元音字母 为（a, e, i, o, u）。

        String str = "abciiidddeeeeef";
        int k = 6;
        int maxLen = 0;

        for(int i=0; i<str.length()-k+1; i++){

            String subStr = str.substring(i, i+k);
            int count = hasYuanYin(subStr);

            maxLen = Math.max(maxLen, count);
            

        }

        System.out.println(maxLen);


    }

    private static int hasYuanYin(String subStr){

        int count = 0;

        for(char c : subStr.toCharArray()){

            if(c == 'a' || c == 'e' || c == 'i' || c == '0' || c == 'u'){

                count++;
            }
        }

        return count;

    }
}


